The present invention relates to public key cryptography.
The increasing use and sophistication of data transmission in such fields as telecommunications, networking, cellular communication, wireless communications, xe2x80x9csmart cardxe2x80x9d applications, audio-visual and video communications has led to an increasing need for systems that permit data encryption, authentication and verification.
It is well known that data can be encrypted by utilizing a pair of keys, one of which is public and one of which is private. The keys are mathematically related such that data encrypted with the public key may only be decrypted with the private key and conversely, data encrypted with the private key can only be decrypted with the public key. In this way, the public key of a recipient may be made available so that data intended for that recipient may be encrypted with the public key and only decrypted by the recipient""s private key, or conversely, encrypted data sent can be verified as authentic when decrypted with the sender""s public key.
The most well known and accepted public key cryptosystems are those based on integer factorization and discrete logarithms in finite groups. In particular, the RSA system for modulus n=pxc2x7q where p and q are primes, the Diffie-Hellman key exchange and the ElGamal protocol in Z*p, (p a prime) have been implemented worldwide.
The RSA encryption scheme, where two primes p and q are multiplied to provide a modulus n, is based on the integer factorization problem. The public key e and private key d are related such that their product exc2x7d equals 1(modxcfx86) where xcfx86=(pxe2x88x921) (qxe2x88x921). A message M is encrypted by exponentiating it with the private key e to the modulus n, [C=M* (mod n)] and decrypted by exponentiating with the public key mod n [M=Cd (mod n)]. This technique requires the transmission of the modulus n and the public key and the security of the system is based on the difficulty of factoring a large number that has no relatively small factors. Accordingly both p and q must be relatively large primes.
One disadvantage of this system is that p and q must be relatively large (at least 512 bits) to attain an adequate level of security. With the RSA protocol this results in a 1024 bit modulus and a 512 bit public key which require significant bandwidth and storage capabilities. For this reason researchers have looked for public key schemes which reduce the size of the public key. Moreover, recent advances in analytical techniques and associated algorithms have rendered the RSA encryption scheme potentially vulnerable and accordingly raised concerns about the security of such schemes. This implies that larger primes, and therefore a larger modulus, need to be employed in order to maintain an acceptable level of security. This in turn increases the bandwidth and storage requirements for the implementation of such a scheme.
Since the introduction of the concept of public key cryptography by Diffie and Hellman in 1976, the potential for the use of the discrete logarithm problem in public key cryptosystems has been recognized. In 1985, ElGamal described an explicit methodology for using this problem to implement a fully functional public key cryptosystem, including digital signatures. This methodology has been refined and incorporated with various protocols to meet a variety of applications, and one of its extensions forms the basis for a proposed U.S. digital signature standard (DSS). Although the discrete logarithm problem, as first employed by Diffie and Hellman in their public key exchange algorithm, referred explicitly to the problem of finding logarithms with respect to a primitive element in the multiplicative group of the field of integers modulo a prime p, this idea can be extended to arbitrary groups (with the difficulty of the problem apparently varying with the representation of the group).
The discrete logarithm problem assumes that G is a finite group, and a and b are elements of G. Then the discrete logarithm problem for G is to determine a value x (when it exists) such that ax=b. The value for x is called a logarithm of b to the base of a, and is denoted by logab.
The difficulty of determining this quantity depends on the representation of C. For example, if the abstract cyclic group of order m is represented in the form of the integers modulo m, then the solution to the discrete logarithm problem reduces to the extended Euclidean algorithm, which is relatively easy to solve. However, the problem is made much more difficult if m+1 is a prime, and the group is represented in the form of the multiplicative group of the finite field Fm+1. This is because the computations must be performed according to the special calculations required for operating in finite fields.
It is also known that by using computations in a finite field whose members lie on an elliptic curve, that is by defining a group structure G on the solutions of y2+xy=x3+ax2+b over a finite field, the problem is again made much more difficult because of the attributes of elliptic curves. Therefore, it is possible to attain an increased level of security for a given size of key. Alternatively a reduced key may be used to maintain a required degree of security.
The inherent security provided by the use of elliptic curves is derived from the characteristic that an addition of two points on the curve can be defined as a further point that itself lies on the curve. Likewise the result of the addition of a point to itself will result in another point on the curve. Therefore, by selecting a starting point on the curve and multiplying it by an integer, a new point is obtained that lies on the curve. This means that where P=(x,y) is a point on an elliptic curve over a finite field [E(Fqn)], with x and y each represented by a vector of n elements then, for any other point Rxcex5 less than P greater than  (the subgroup generated by P), dP=R. To attack such a scheme, the task is to determine an efficient method to find an integer d, 0xe2x89xa6dxe2x89xa6(order of P)xe2x88x921 such that dP=R. To break such a scheme, the best algorithms known to date have running times no better than 0({square root over (p)}), where p is the largest prime dividing the order of the curve (the number of points on the curve).
Thus, in a cryptographic system where the integer d remains secret, the difficulty of determining d can be exploited.
An ElGamal protocol of key exchange based on elliptic curves takes advantage of this characteristic in its definition of private and public keys. Such an ElGamal protocol operates as follows:
1. In order to set up the protocol, where a message is to be sent from A to B, an elliptic curve must be selected and a point P=(x,y), known as the generating point, must be selected.
2. The receiver, B, then picks a random integer d as his private key. He then computes dP, which is another point on the curve, which becomes his public key that is made available to the sender and the public. Although the sender knows the value dP, due to the characteristic of elliptic curves noted above, he has great difficulty determining the private key d.
3. The sender A, chooses another random integer k, the session seed, and computes another point on the curve, kP which serves as a public session key.
This also exploits the characteristic of elliptic curves mentioned above.
4. The sender, A, then retrieves the public key dP of receiver B and computes kdP, another point on the curve, which serves as the shared encryption key for that session.
5. The sender, A, then encrypts the message M with the encryption key to obtain the ciphertext C.
6. The sender then sends the public session key kP and the ciphertext C to the receiver B.
7. The receiver, B, determines the encryption key kdP by multiplying his private key d by kP.
8. The receiver, B, can then retrieve the message M by decrypting the ciphertext C with the encryption key kdP.
During the entire exchange, the private key d and the seed key k remain secret so that even if an interloper intercepts the session key kP he cannot derive the encryption key kdP from B""s public key dP.
Elliptic curve cryptosystems can thus be implemented employing public and private keys and using the ElGamal protocol.
The elliptic curve cryptography method has a number of benefits. First, each person can define his own elliptic curve for encryption and decryption, which gives rise to increased security. If the private key security is compromised, the elliptic curve can be easily redefined and new public and private keys can be generated to return to a secure system. In addition, to decrypt data encoded with the method, only the parameters for the elliptic curve and the session key need be transmitted.
One of the drawbacks of other public key systems is the large bandwidth and storage requirements for the public keys. The implementation of a public key system using elliptic curves reduces the bandwidth and storage requirements of the public key system because the parameters can be stored in fewer bits. Until now, however, such a scheme was considered impractical due to the computational difficulties involved and the requirement for high speed calculations. The computation of kP, dP and kdP used in a key exchange protocol require complex calculations due to the mathematics involved in adding points in elliptic curve fields.
Computations on an elliptic curve are performed according to a well known set of relationships. If K defines any field, then an equation of the form y2+a1xy+a3y=x3+a2x2+a4x+a6, where each of the coefficients ai lie in K, defines an elliptic curve over K. If E is the set of points on this curve, then an abelian group can be defined on the set E∪{0}, where 0 is a special element not occurring in E. 0 acts as the zero element of the group. If P=(x,y), then xe2x88x92P=(x,xe2x88x92y) in the case of an odd characteristic, and for two points P and Q on the curve where Qxe2x89xa0xc2x1P, the sum P+Q is the third point on the curve where the line joining P and Q again meets the curve. If P=Q, then the tangent line is used. As in any abelian group, we use the notation nP to denote P added to itself n times if n is positive, and xe2x88x92P added to itself |n| times if n is negative, and 0P=0.
If Fq is a finite field, then elliptic curves over Fq can be divided into two classes, namely supersingular and non-supersingular curves. If Fq is of characteristic 2, i.e. q=2M, then the classes are defined as follows.
i) The set of all solutions to the equation y2+ay=x3+bx+c where a,b,cxcex5Fq, axe2x89xa00, together with a special point called the point at infinity 0 is a supersingular curve over Fq.
ii) The set of all solutions to the equation y2+xy=x3+ax2+b where a,bxcex5Fg, bxe2x89xa00, together with a special point called the point at infinity 0 is a non-supersingular curve over Fq.
By defining an appropriate addition on these points, we obtain an additive abelian group. The addition of two points P(x1, y1) and Q(x2, y2) for the supersingular elliptic curve E with y2+ay=x3+bx+C is given by the following:
If P=(x1, y2)xcex5E; then define xe2x88x92P=(x2, y1+a), P+0=0+P=P for all Pxcex5E.
If Q=(x2, y2)xcex5E and Qxe2x89xa0xe2x88x92P, then the point representing the sum of P+0, is denoted (x3, y3), where       x    3    =      {                                        (                                                            y                  1                                ⊕                                  y                  2                                                                              x                  1                                ⊕                                  x                  2                                                      )                    2                ⊕                  x          1                ⊕                              x            2                    ⁢                      xe2x80x83                    ⁢                      (                          P              ≠              Q                        )                    ⁢                      
                    ⁢          or          ⁢                      
                    ⁢                      x            3                              =              {                                                                              x                  1                  4                                ⊕                                  b                  2                                                            a                2                                      ⁢                          xe2x80x83                        ⁢                          (                              P                =                Q                            )                        ⁢                          
                        ⁢            and            ⁢                          
                        ⁢                          y              3                                =                      {                                                                                (                                                                                            y                          1                                                ⊕                                                  y                          2                                                                                                                      x                          1                                                ⊕                                                  x                          2                                                                                      )                                    ⁢                                      (                                                                  x                        1                                            ⊕                                              x                        3                                                              )                                                  ⊕                                  y                  1                                ⊕                                  a                  ⁢                                      xe2x80x83                                    ⁢                                      (                                          P                      ≠                      Q                                        )                                    ⁢                                      
                                    ⁢                  or                  ⁢                                      
                                    ⁢                                      y                    3                                                              =                              {                                                                            (                                                                                                    x                            1                            2                                                    ⊕                          b                                                a                                            )                                        ⁢                                          (                                                                        x                          1                                                ⊕                                                  x                          3                                                                    )                                                        ⊕                                      y                    1                                    ⊕                                      a                    ⁢                                          xe2x80x83                                        ⁢                                          (                                              P                        =                        Q                                            )                                                                                                              
The addition of two points P(x1, y1) and Q(x2, y2) for the non-supersingular elliptic curve y2+xy=x3+ax2+b is given by the following:
If P=(x1, y2)xcex5E then define xe2x88x92P (x1, y1+x1). For all Pxcex5E, 0+P=P+0=P. If Q=(x2, y2)xcex5E and Qxe2x89xa0xe2x88x92P, then P+Q is a point (x3, y3) where       x    3    =      {                                        (                                                            y                  1                                ⊕                                  y                  2                                                                              x                  1                                ⊕                                  x                  2                                                      )                    2                ⊕                                            y              1                        ⊕                          y              2                                                          x              1                        ⊕                          x              2                                      ⊕                  x          1                ⊕                  x          2                ⊕                  a          ⁢                      xe2x80x83                    ⁢                      (                          P              ≠              Q                        )                    ⁢                      
                    ⁢          or          ⁢                      
                    ⁢                      x            3                              =              {                                            x              1              2                        ⊕                                          b                                  x                  1                  2                                            ⁢                              xe2x80x83                            ⁢                              (                                  P                  =                  Q                                )                            ⁢                              
                            ⁢              and              ⁢                              
                            ⁢                              y                3                                              =                      {                                                                                (                                                                                            y                          1                                                ⊕                                                  y                          2                                                                                                                      x                          1                                                ⊕                                                  x                          2                                                                                      )                                    ⁢                                      (                                                                  x                        1                                            ⊕                                              x                        3                                                              )                                                  ⊕                                  x                  3                                ⊕                                                      y                    1                                    ⁢                                      xe2x80x83                                    ⁢                                      (                                          P                      ≠                      Q                                        )                                    ⁢                                      
                                    ⁢                  or                  ⁢                                      
                                    ⁢                                      y                    3                                                              =                              {                                                      x                    1                    2                                    ⊕                                                            (                                                                        x                          1                                                ⊕                                                                              y                            1                                                                                x                            1                                                                                              )                                        ⁢                                          x                      3                                                        ⊕                                                            x                      3                                        ⁢                                          xe2x80x83                                        ⁢                                          (                                              P                        =                        Q                                            )                                                                                                              
Accordingly it can be seen that computing the sum of two points on E requires several multiplications, additions, and inverses in the underlying field Fq. In turn, each of these operations requires a sequence of elementary bit operations
When implementing an ElGamal or Diffie-Hellman scheme with elliptic curves, one is required to compute kP=P+P+. . . +P (P added k times) where k is a positive integer and Pxcex5E. This requires the computation of (X3, y3) to be computed kxe2x88x921 times. Even if alternative techniques such as xe2x80x9cdouble and addxe2x80x9d are utilised, it is still necessary to compute the addition of two points several times, each of which requires multiplications, additions and inverses in the underlying finite field. For large values of k which are typically necessary in cryptographic applications, this has previously been considered impractical for data communication.
It is an object of the present invention to provide a method of encryption utilizing elliptic curves that facilitates the computation of additions of points while providing an adequate level of security in an efficient and effective manner.
The applicants have developed a method using a modified version of the Diffie-Hellman and ElGamal protocols defined in the group associated with the points on an elliptic curve over a finite field. The method involves formulating the elliptic curve calculations so as to make elliptic curve cryptography efficient, practical and viable, and preferably employs the use of finite field processor such as the Computational Method and Apparatus for Finite Field Multiplication as disclosed in U.S. Pat. No. 4,745,568. The preferred method exploits the strengths of such a processor with its computational abilities in finite fields. The inventive method structures the elliptic curve calculations as finite field multiplication and exponentiation over the field P2m. In the preferred method, a normal basis representation of the finite field is selected and the calculations which can readily be performed on a finite field processor.
The inventors have recognized that the computations necessary to implement the elliptic curve calculations can be performed efficiently where a finite field of characteristic 2 is chosen.
When computing in a field of characteristic 2, i.e. F2m, squaring is a linear operation, i.e. (A+B)2 is A2+B2. By adapting appropriate representations, the computation of the squared terms required in the addition of two points is greatly simplified. In particular, if a normal basis representation is chosen, squaring can be achieved through a cyclic shift of the binary vector representing the field element to be squared.
Moreover, computing inverses in F2m can be implemented with simple shift and XOR operations by selection of an appropriate representation. In some implementations, the computation of an inverse can be arranged to utilize multiple squaring operations and thereby improve the efficiency of the computation.
When such computations are performed using a normal basis representation of the finite field, the inventors have also recognized that the elliptic curve calculations are further simplified with the computations presented in this form, the applicants have realized that specialized semiconductor devices can be fabricated to perform the calculations. With the calculations presented in such a form, additions in the field F2m can be efficiently performed in one clock cycle utilizing a simple XOR operation.
Multiplications can be performed very efficiently in only n clock cycles where n is the number of bits being multiplied. Furthermore, squaring can be efficiently performed in 1 clock cycle as a cyclic shift of the bit register. Finally, inverses can easily be computed, requiring approximately log2n multiplications rather than the approximately 2n multiplications required in other arithmetic systems.
The inventors have also recognized that the bandwidth and storage requirements of a cryptographic system utilizing elliptic curves can be significantly reduced where for any point P(x,y) on the curve, only the x coordinate and one bit of the y coordinate need be stored and transmitted, since the one bit will indicate which of the two possible solutions is the second coordinate.
The inventors have also recognized when using the ElGamal protocol that messages need not be points on the curve if the protocol is modified such that the message M is considered as a pair of field elements M1M2 and each is operated on by the coordinates (x1y) of the session encryption key kdP in a predetermined manner to produce new field elements C1C2 that represent the ciphertext C. The receiver can then extract the message M=(m1, m2) by applying the inverse transformation of the predetermined manner. Although this may require an inverse operation in the field, they may be performed efficiently in the field F2155, and in particular when operating with the processor noted above.
To assist in the appreciation of the implementation of the present invention, it is believed that a review of the underlying principles of finite field operations is appropriate. The finite field F2 is the number system in which the only elements are the binary numbers 0 and 1 and in which the rules of addition and multiplication are the following:
0+0=1+1=0
0+1=1+0=1
0xc3x970=1xc3x970=0xc3x971=0
1xc3x971=1
These rules are commonly called modulo-2 arithmetic. All additions specified in logic expressions or by adders in this application are performed modulo2 as an XOR operation. Furthermore, multiplication is implemented with logical AND gates.
The finite field F2m, where m is an integer greater than 1, is the number system in which there are 2m elements and in which the rules of addition and multiplication correspond to arithmetic modulo an irreducible polynomial of degree D with coefficients in F2. Although in an abstract sense there is for each m only one field F2m, the complexity of the logic required to perform operations in F2m depends strongly on the particular way in which the field elements are represented. These operations may be performed using processors implemented in either hardware or software with dedicated hardware processors generally considered faster.
The conventional approach to operations performed in F2m is described in such papers as T. Bartee and D. Schneider, xe2x80x9ccomputation with Finite Fieldsxe2x80x9d, Information and Control, Vol. 6, pp. 79-98, 1963. In this conventional approach, one first chooses a polynomial P(X) of degree m which is irreducible over F2m, that is, P(X) has binary coefficients but cannot be factored into a product of polynomials with binary coefficients each of whose degree is less than m. An element A in F2m is then defined to be a root of P(X), that is, to satisfy P(A)=0. The fact that P(X) is irreducible guarantees that the m elements A0=1, A, A2, . . . Amxe2x88x921 of F2m are linearly independent over F2.
For the purposes of illustration, the example of F2e will be used with the choice of P(X)=X3+X+1 for the irreducible polynomial of degree 3. The next step is to define A as an element of F2, such that A3+A+1=0. The following assignment of unit vectors is then made:
A0=1=[1,0,0]
A1=[0,1,0]
A2=[0,0,1]
An arbitrary element B of F2, is now represented by the binary vector [b2, b1, b0] with the meaning that B=[b2, b2, b0]=b2A2+b2A+b0.
If we represent a second element C=[c2, c1, c0], it follows that B+C=[b2⊕c2, b2⊕c2, b0⊕c0].
Thus, in the conventional approach, addition in F2e is easily performed by logic that merely forms the modulo-2 sum of the two vectors representing the elements to be summed component-by-component. Multiplication is, however, considerably more complex to implement.
Continuing the example, from the irreducible polynomial it can be seen that A3=A+1 and A4=A2+A where use has been made of the fact that xe2x88x921+1 in F(2). In hardware, multiplication can be simplified by taking advantage of the special feature of a finite field F2m that there always exists a so-called normal basis for the finite field. That is, one can always find a field element N such that N , N2, N4 . . . N2mxe2x88x921 are a basis for F2m. Every field element B can be uniquely written as B=bmxe2x88x921N2mxe2x88x922+. . . +b2N6+b2N2+b0N=[bmxe2x88x921 . . . , b2, b1, b0] where b0, b2, b2, . . . bmxe2x88x921 are binary digits.
For example, in the finite field F23, if we let N=[1,1,0]
Then, if B=[bmxe2x88x921, . . . , b2, b2, b0] and C=[cmxe2x88x921, . . . , c2, c1, c0] are any two elements of F2m in normal basis representation, then the product D=Bxc3x97C=[dmxe2x88x921, . . . , d2, d1, d0] has the property that the same logic circuitry which when applied to the components or binary digits of the vectors representing B and C produces dmxe2x88x921 will sequentially produce the remaining components dmxe2x88x922, . . . , d2, d1, d0 of the product when applied to the components of the successive shifts of the vectors representing B and C.
As illustrated in U.S. Pat. No. 4,745,568 for Computational Method and Apparatus for Finite Field Multiplication, multiplication may be implemented by storing bit vectors B and C in respective shift registers and establishing connections to respective accumulating cells such that a grouped term of each of the expressions d1 is generated in respective ones of m accumulating cells. By rotating the bit vectors B and C in the shift registers and by rotating the contents of the accumulating cells, each grouped term of a respective binary digit d, is accumulated in successive cells. Thus all of the binary digits of the product vector are generated simultaneously in the accumulating cells after one complete rotation of the bit vectors B and C.
One attribute of operating such a processor is that in the field F2m, is that squaring is a linear operation in the sense that for every pair of elements B and C in F2m, (B+C)2=B2+C2. It is the case for every element B of F2m that B2m=B.
In particular in a normal basis representation, squaring an element involves a cyclic shift of the vectors representation of the element, i.e. if B=[bmxe2x88x921, . . . , b2, b1, b0] then B2=[bmxe2x88x922, . . . , b2, b1, b0, bmxe2x88x921].
Thus when using the processor exemplified above, squaring may be achieved in one cycle. Moreover, this general characteristic of F2m, where squaring is a linear operation, may be exploited in other implementations, such as software, where a normal basis representation is not used.
As noted above, the inventors have taken advantage of the efficiency of the mathematical operations in F2m in the implementation of an elliptic curve encryption scheme. The applicants have developed a method of formulating the elliptic curve calculations so as to make elliptic curve cryptography efficient, practical and viable. The preferred method employs the use of a finite field processor such as the Computational Method and Apparatus for Finite Field Multiplication as disclosed in U.S. Pat. No. 4,745,568. The method couples the attractive cryptographic characteristics of elliptic curves with the strengths of the field processor through its computational abilities in finite field F2m. The inventive method structures the elliptic curve calculations as operations, such as multiplication and exponentiation, over the field where F2m, which can readily be calculated on a finite field processor.